# -*- coding: utf-8 -*-
# @Time: 2021/8/13 14:18
# @File: problem-160.py
# @DESC: https://leetcode-cn.com/problems/intersection-of-two-linked-lists/
# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        print("找两个链表值相等的节点")

        visited = set()

        tempA = headA
        while tempA:
            visited.add(tempA)
            tempA = tempA.next
        tempB = headB
        while tempB:
            if tempB in visited:
                return tempB
            else:
                tempB = tempB.next

        return None


    def listToNode(self, data):
        head = ListNode(0)
        p = head
        for i in data:
            p.next = ListNode(i)
            p = p.next
        return head.next


solution = Solution()

listA = [4, 1, 8, 4, 5]
listB = [5, 0, 1, 8, 4, 5]

l1 = solution.listToNode(listA)
l2 = solution.listToNode(listB)

result = solution.getIntersectionNode(l1, l2)


